package com.dragon.datastructure.linkedlist;

/**
 * 虚拟头节点的单向链表
 *
 * @author dragon
 * @since 2019/11/20
 */
public class DummyHeadSingleLinkedList<E extends Comparable<E>> {

    /**
     * 虚拟头节点，该虚拟头节点是一个入口，通过它能够知道链表
     */
    private Node<E> dummyHeadNode;

    /**
     * 该链表总共有多少个元素
     */
    private int size;

    public DummyHeadSingleLinkedList() {
        dummyHeadNode = new Node<>(null, null);
        this.size = 0;
    }

    public void reversePrint() {
        reversePrint(this.dummyHeadNode.next);
    }

    private void reversePrint(Node head) {
        if (head == null) {
            return;
        }
        reversePrint(head.next);
        System.out.print(head.item + " ");
    }

    /**
     * 内部的真正存储元素的节点
     * <p>
     * 1.为什么用private,因为这个Node类是我自己内部维护的,用户不需要知道内部的实现细节
     * 2.为什么是static，因为这个Node类本身就是独立的，它不依附于DummyHeadSingleLinkedList
     */
    private static class Node<E> {
        /**
         * 存储的具体元素
         */
        E item;

        /**
         * 该节点的下一个节点(通过存储的next节点来维护节点与节点之间的关系)
         */
        Node<E> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    /**
     * 通过索引来找到相对应的Node节点
     *
     * @param index 索引
     * @return
     */
    private Node<E> node(int index) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("index out of bound: index=" + index);
        }
        Node tmp = dummyHeadNode;
        for (int i = 0; i <= index; i++) {
            tmp = tmp.next;
        }

        return tmp;
    }

    /**
     * 在尾部添加一个元素
     *
     * @param element
     */
    public void addLast(E element) {
        add(size, element);
    }

    /**
     * 在尾部添加元素
     *
     * @param e 待添加的元素
     */
    public void add(E e) {
        dummyHeadNode.next = add(dummyHeadNode.next, e);
    }

    private Node<E> add(Node<E> head, E e) {
        if (head == null) {
            return new Node<>(e, null);
        }
        head.next = add(head.next, e);

        return head;
    }

    /**
     * 删除链表中的指定的元素
     *
     * @param e
     */
    public void remove(E e) {
        dummyHeadNode.next = remove(dummyHeadNode.next, e);
    }

    private Node<E> remove(Node<E> head, E e) {
        if (head == null) {
            return null;
        }
        if (head.item.equals(e)) {
            return head.next;
        } else {
            head.next = remove(head.next, e);

            return head;
        }
    }

    /**
     * 判断链表中是否包含e这个元素
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {

        return contains(dummyHeadNode.next, e);
    }


    private boolean contains(Node<E> head, E e) {
        if (head == null) {
            return false;
        }

        if (head.item.equals(e)) {
            return true;
        } else {
            return contains(head.next, e);
        }
    }

    /**
     * 从头开始添加一个元素
     *
     * @param element
     */
    public void addFirst(E element) {
        add(0, element);
    }

    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new RuntimeException("index out of bound: index=" + index);
        }
        // 1.找到需要插入到index角标的上一个元素，不管你是要插入到哪里，你都需要找到你的插入index元素的上一个元素，你只有找到你的上一个元素，你就能够找到你需要维护的下一个元素
        Node<E> pre = index == 0 ? dummyHeadNode : node(index - 1);
        // 2.创建节点，并维护关系
        pre.next = new Node<>(element, pre.next);
        // 3.维护size变量
        size++;
    }

    public void addOrder(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element don't be null");
        }
        Node<E> cur = this.dummyHeadNode.next;
        Node<E> prev = this.dummyHeadNode;
        while (cur != null) {
            if (element.compareTo(cur.item) <= 0) {
                break;
            }
            prev = cur;
            cur = cur.next;
        }
        prev.next = new Node<>(element, cur);
        size++;
    }

    /**
     * 合并两个有序的单链表，合并之后的链表依然有序
     *
     * @param n1 有序列表 n1
     * @param n2 有序列表 n2
     * @return 合并之后的有序节点
     */
    public Node mergeTwoLists(Node<E> n1, Node<E> n2) {
        Node<E> dummyHead = new Node<>(null, null);
        Node<E> prevNode = dummyHead;
        while (n1 != null && n2 != null) {
            if (n1.item.compareTo(n2.item) < 0) {
                prevNode.next = n1;
                n1 = n1.next;
            } else {
                prevNode.next = n2;
                n2 = n2.next;
            }
            prevNode = prevNode.next;
        }
        prevNode.next = n1 == null ? n2 : n1;

        return dummyHead.next;
    }

    /**
     * 替换元素，返回旧元素
     *
     * @param index
     * @param element
     * @return
     */
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("index out of bound: index=" + index);
        }
        Node<E> node = node(index);
        E oldVal = node.item;
        node.item = element;

        return oldVal;
    }

    /**
     * 删除指定索引处的角标，返回被删除的元素
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        Node<E> prev = node(index - 1);
        Node<E> deleteNode = prev.next;
        prev.next = deleteNode.next;
        E oldVal = deleteNode.item;
        deleteNode.next = null;
        deleteNode.item = null;
        size--;

        return oldVal;
    }

    /**
     * 通过索引获得元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        Node<E> node = node(index);
        return node.item;
    }

    /**
     * 判断链表是否为空链表
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 得到链表的元素个数
     *
     * @return
     */
    public int size() {
        return size;
    }

    public void removeElements(int val) {
        Node prev = dummyHeadNode;
        while (prev.next != null) {
            if (prev.next.item.equals(val)) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }

    }

    public static void main(String[] args) {
        DummyHeadSingleLinkedList<Integer> list = new DummyHeadSingleLinkedList<>();
        list.addLast(1);
        list.addFirst(23);
        list.addFirst(1);
        list.addLast(45);
        list.addLast(1);
        list.removeElements(1);
        System.out.println(list);
    }

    /**
     * 重写toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("head");
        for (Node<E> cur = dummyHeadNode.next; cur != null; cur = cur.next) {
            sb.append(cur.item + "->");
        }
        sb.append("NULL\n");
        sb.append("size:" + size);
        return sb.toString();
    }

}
